This phase I study proposes to evaluate safety and pharmacokinetics of thalidomide in HIV-positive patients. Study rationale is that one of the effects of thalidomide is inhibition of TNF-alpha production by monocytes. Preliminary data in 10 patients with HIV infection treated with thalidomide at the Rockefeller University suggest that 300 mg thalidomide was not well tolerated. However lower doses have been fairly well tolerated. This study will use three dosage regimens, twelve subjects will be enrolled in each cohort. After a subject has been enrolled into a cohort, he/she will be randomized to receive either thalidomide or matching placebo. The ratio of individuals receiving thalidomide versus placebo will be 3:1. If more than 2 out of 9 subjects receiving thalidomide in a single cohort experience dose-limiting toxicity, enrollment in that cohort will be discontinued and the dose level in the previous cohort will be considered the maximum tolerated dose.